Querying Shortest Paths

The CubeDatabase class provides the shortestPath() method, that takes the network name and the query definition arguments.

The query definition is defined by using the ShortestPathQuery method. This serves as a container set for the various parameters that may be used within a shortest path query. These arguments are the following:

The initial node (called origin). This can be a centroid or a network node.
The final node (called destination). This can be a centroid or a network node.
The cost expression that is minimized when calculating the shortest path, which uses Lua expressions.
A Boolean that is defining if to include centroid connectors or not in the calculation of the shortest path.
A LinkEntryVector, defined based on LinkEntry, to exclude links from the path building process.

An example of a single distance-based path between two centroid nodes is defined below, printing the sequence of links and their cost.

db = cp.CubeDatabase(source_db, False)

node_start = 24  
node_end = 19  

# Defining the cost measure for shortest-path calculation 
cost_lua_expression = "cost(link.distance)"

# Excluding links vector
exclude_vector = cp.LinkEntryVector()
x = cp.LinkEntry(600, 601)
exclude_vector.append(x)

query_definition = cp.ShortestPathQuery(node_start, node_end, cost_lua_expression, False, exclude_vector)
path = db.shortestPath(network_name, query_definition)

for path_link in path.links: 
    print(path_link.a, path_link.b, path_link.cost)

It is possible to use a list of node pairs and use the ShortestPathQueryVector() to append multiple ShortestPathQuery statements for queries definition. The shortestPaths(network_name, queries_definition) method will generate the shortest path for all the pairs of nodes. An example is provided below.

db = cp.CubeDatabase(source_db, False)

start_end_nodes_list = [(690, 685), (685, 448), (448, 742), (742, 758)]
cost_expression = "cost(link.distance)"  # (Lua expression)

# Excluding links vector (none in this example
exclude_vector = cp.LinkEntryVector()

queries_definition = cp.ShortestPathQueryVector()

for node_start, node_end in start_end_nodes_list:
    queries_definition.append(cp.ShortestPathQuery(node_start, node_end, cost_expression, False, exclude_vector))

paths = db.shortestPaths(network_name, queries_definition)

path_index = 0
for path in paths:
    node_start = start_end_nodes_list[path_index][0]
    node_end = start_end_nodes_list[path_index][1]
    if len(path.links) == 0:
        print(f"No path found from {node_start} to {node_end} under these conditions")
    else:
        print(f"The path from {node_start} to {node_end} is formed of a sequence of", len(path.links), "links")
        sum_cost = 0
        for path_link in path.links:
            sum_cost += path_link.cost
            print(f"{path_link.a:<10}",
                  f"{path_link.b:<10}",
                  f"{path_link.cost:<10,.3f}",
                  f"{sum_cost:<10,.3f}")
    path_index += 1